Méthodes par différences temporelles n-Step (n-step TD Methods)

3.Contrôle avec la méthode n-step Sarsa

Principe de fonctionnement

Comment peut-on utiliser les méthodes n-step non plus uniquement pour la prédiction mais pour le contrôle ? Une manière simple est de combiner la méthode Sarsa et la méthode n-step afin de réaliser une méthode de contrôle de type on-policy. La version Sarsa que nous avons vu précédemment est donc une méthode Sarsa(0).

L'idée est simplement de remplacer les états par les paires d'état-action et d'utiliser ensuite une stratégie de type ɛ-greedy. On définit les revenus obtenus par la méthodes n-step à partir des paires d'état-action:

$${G_{t:t + n}} = {R_{t + 1}} + \gamma {R_{t + 2}} + ... + {\gamma ^{n - 1}}{R_{t + n}} + {\gamma ^n}{Q_{t + n - 1}}\left( {{S_{t + n}},{A_{t + n}}} \right),\quad n \ge 1,\quad0 \le t \le T - n$$

avec ${G_{t:t + n}} = {G_t}$ si $(t+n) \ge T$.

L'équation utilisée dans l'algorithme est alors:

$${Q_{t + n}}\left( {{S_t},{A_t}} \right) = {Q_{t + n - 1}}\left( {{S_t},{A_t}} \right) + \alpha \left[ {{G_{t:t + n}} - {Q_{t + n - 1}}\left( {{S_t},{A_t}} \right)} \right], \quad 0 \le t \le T$$

les valeurs de tous les autrres états restant inchangées: ${Q_{t + n}}\left( {s,a} \right) = {Q_{t + n - 1}}\left( {s,a} \right)$ pour tous les états $s \ne S_t$ et les actions $a \ne A_t$

Algorithme